package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName: TopVotedCandidate
 * @Description TODO
 * @Author skywingking
 * @Date 2021/12/11 11:27 下午
 **/
public class TopVotedCandidate {
    private List<Integer> topsTVC;
    private Map<Integer,Integer> voteCountsTVC;
    private int[] timesTVC;
    public TopVotedCandidate(int[] persons, int[] times) {
        topsTVC = new ArrayList<>();
        voteCountsTVC = new HashMap<>();
        voteCountsTVC.put(-1,-1);
        int top = -1;
        for(int i = 0;i < persons.length;i++){
            int p = persons[i];
            voteCountsTVC.put(p,voteCountsTVC.getOrDefault(p,0) + 1);
            if(voteCountsTVC.get(p) >= voteCountsTVC.get(top)){
                top = p;
            }
            topsTVC.add(top);
        }
        this.timesTVC = times;
    }

    public int qTVC(int t) {
        int l = 0, r = timesTVC.length - 1;
        while(l < r){
            int m = l + (r - l + 1) / 2;
            if(timesTVC[m] <= t){
                l = m;
            }else{
                r = m - 1;
            }
        }
        return topsTVC.get(l);
    }
}